Network Address Translation (NAT) is the process of modifying IP address information in network traffic (e.g., IPv4 traffic) headers while in transit across a traffic routing device. The traffic routing device that performs the IP address modification is referred to as an NAT device. NAT became a popular tool for alleviating the consequences of IPv4 address exhaustion. It has become a common feature in routers for home and small-office Internet connections. NAT device hides an entire IP address space, usually consisting of private IP addresses, behind a single IP address in another (usually public) address space. For example, the single IP address belongs to the NAT device in the public address space and is assigned to all packets in a flow originated from a host device hidden from the public address space behind the NAT device. In other words, the single IP address replaces the host device's private IP addresses and is common across all packets in the flow modified by the NAT device. To avoid ambiguity in the handling of returned packets, an one-to-many NAT device uses higher level information, such as TCP/UDP ports in outgoing packets, possibly altering it when required to avoid ambiguity, and maintains a translation table so that return packets can be correctly translated back. However, such higher level information and translation table is not available outside of the NAT device.